package com.zds.leetcode;

import java.util.LinkedList;
import java.util.List;

public class q_99 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(2);
        recoverTree(root);
        TreeNode.printTreeNode(root);
    }

    public static void swapTwoEle(TreeNode root, int x, int y) {
        if (root != null) {

            if (root.val == x || root.val == y) {
                // 给 flag 设置为另外一个元素的值，后面改为匹配 flag
                // 交换被找到节点的值
                root.val = root.val == x ? y : x;
            }
        }

        if (root.left != null) swapTwoEle(root.left, x, y);
        if (root.right != null) swapTwoEle(root.right, x, y);
    }


    public static void inroder(TreeNode root, List<Integer> nums) {
        if (root == null) {
            return;
        }
        if (root.left != null) inroder(root.left, nums);
        nums.add(root.val);
        if (root.right != null) inroder(root.right, nums);
    }

    public static int[] findTwoSwapped(List<Integer> nums) {
        // 1 2 3 4 5
        // 1 4 3 2 5
        // 可知 如果一个有序数组中两个元素交换了位置，我们从0遍历i元素和i+1元素(i<arr.size)
        // 先找到第二个元素偏大值  如果 nums[i] > nums[i+1] 说明 i 是被交换的第一个元素
        // 第一个元素偏小值
        boolean firstPair = false;
        int index1 = -1, index2 = -1;
        for (int i = 0; i < nums.size() - 1; i++) {
            // 找第一次匹配到的异常
            if (!firstPair && nums.get(i) > nums.get(i + 1)) {
                index2 = i;
                firstPair = true;
                continue;
            }
            // 找第二次匹配异常
            if (firstPair && nums.get(i) > nums.get(i + 1)) {
                index1 = i + 1;
            }
        }
        // TODO 如果两个元素相邻
        // 此时 index1 = -1 此时交换的是两个相邻元素
        if (index1 == -1) {
            index1 = index2;
            index2 = index2+1;
        }
        return new int[]{nums.get(index1), nums.get(index2)};
    }

    public static void recoverTree(TreeNode root) {
        // 中序遍历二叉树得到数组
        List<Integer> nums = new LinkedList<>();

        // 可知正常情况，中序遍历二叉搜索树得到的是一个有序数组
        inroder(root, nums);
        // 问题转换为 如果交换了二叉搜索树两个节点位置，其实相当于把一个有序数组的两个元素交换了位置
        // 要找出这两个元素
        int[] swapped = findTwoSwapped(nums);
        // 然后在二叉搜索树中找到这两个元素分别用另外一个值替换掉
        swapTwoEle(root, swapped[0], swapped[1]);
    }
}
